/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package lk;

import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;

/**
 *
 * @author apple
 */
public class Grasp {
       
    public static final double alpha = 0.45 ;
    public ArrayList<Vuelo> solucion ;
    public ArrayList<Vuelo> solucionBest ;
    public ArrayList<Vuelo> usados ;
    public Almacen or ;
    public Almacen dest ;
    public int continental ;
    
    public Grasp(){
    }
    
    public int getRangoHora( int serv ){
        serv = 3 ;
        int resp ;
        switch( serv ){
            case 0: resp = 8 ; break ;
            case 1: resp = 16 ; break ;
            case 2: resp = 24 ; break ;
            default: resp = 48 ; break ;
        }
        return resp ;
    }
    
    public void print( ArrayList<Double> data ) throws IOException{
        FileWriter fw = new FileWriter( "output.in" ) ;
        PrintWriter pw = new PrintWriter( fw ) ;
        
        if( data.isEmpty() ){
            pw.println( "No se encontró ruta" ) ;
        }
        
        String t[] = new String[ 4 ] ;
        t[ 0 ] = "Tiempo total " ;
        t[ 1 ] = "Costo total " ;
        t[ 2 ] = "Distancia total " ;
        
        for(int i = 0 ; i < data.size() ; i++){
            pw.println( t[ i ] + "= " + data.get( i ) ) ;
        }
        pw.close() ;
    }
    
    public int getMaxIteraciones(){
        return 1000 ;
    }
    
    public double funObj(ArrayList<Vuelo> vuelos){
//        int recorrido = 0;
        double costo = 0;
        for(int i = 0; i < vuelos.size(); i++){
            costo += vuelos.get(i).costo;
        }
        return costo;
    }

    
    private boolean almacenDisponible(Almacen almacen, Fecha fechaInicio, Fecha fechaFin){
        /*Verificar disponibilidad del almacen entre fechaInicio y fechaFIn*/
        
        //Genero sumatoria de reservas del alamcen entre fInicio y fFin
        //Comparo esta sumatoria con su capacidad
        int cantReservas = 0;
        
        for( ReservaAlmacen resActual : LinKernighan.arReserva ){
            //if ((almacen == reservaActual.almacen && (fechaInicio.esMenorQue(reservaActual.fechaIngresoAprox) &&
            //        reservaActual.fechaSalidaAprox.esMenorQue(fechaFin))))
            if( almacen.same( resActual.almacen ) &&  
                ( (fechaInicio.esMenorQue( resActual.fechaIngresoAprox ) && resActual.fechaIngresoAprox.esMenorQue( fechaFin ) ) ||
                ( fechaInicio.esMenorQue( resActual.fechaSalidaAprox )  && resActual.fechaSalidaAprox.esMenorQue( fechaFin ) )  ||
                ( resActual.fechaIngresoAprox.esMenorQue( fechaInicio ) && fechaFin.esMenorQue( resActual.fechaSalidaAprox ) ) ) )
                cantReservas++;
        }
        
        return ( cantReservas < almacen.capacidad ) ;
    }
    
    private boolean verificarDisponibilidadAlmacenes(Vuelo vueloActual, Fecha fechaRegistroPedido ){
        // FALTA REVISAR BIEN ESTO
        boolean disponibleOrigen = false ;
        boolean disponibleDestino = false ;
        Fecha horaInicioOrigen = null ;
        Fecha horaFinOrigen = null ;
        Fecha horaInicioDestino = null ;
        Fecha horaFinDestino = null;
        Almacen almacenOrigen = vueloActual.origen ;
        
        //Caso: sea un vuelo intermediario de la ruta
        if( solucion.size() > 0 && vueloActual.destino.diff( dest ) ){
            Vuelo ultimoVuelo = getLast() ;
            horaInicioOrigen = ultimoVuelo.fechaLlegada ;
            horaFinOrigen = vueloActual.fechaSalida ;
            horaInicioDestino = vueloActual.fechaLlegada ;
            //Como aún no se sabe la hora de salida del siguiente vuelo:
            horaFinDestino = new Fecha( horaInicioDestino , 1 ) ;
        }
        
        //Caso: sea el primer vuelo de toda la ruta
        if( solucion.size() == 0 ){
            horaInicioOrigen = fechaRegistroPedido ;
            horaFinOrigen = vueloActual.fechaSalida ;
            horaInicioDestino = vueloActual.fechaLlegada ;
            //Como aún no se sabe la hora de salida del siguiente vuelo:
            horaFinDestino = new Fecha( horaInicioDestino , 1 ) ;
        }
        
        //Caso: sea un único vuelo toda la ruta
        if( vueloActual.destino.same( dest ) && solucion.size() == 0 ){
            horaInicioOrigen = fechaRegistroPedido ;
            horaFinOrigen = vueloActual.fechaSalida ;
            horaInicioDestino = vueloActual.fechaLlegada ;
            horaFinDestino = new Fecha( vueloActual.fechaLlegada , Constantes.TOLERANCIA ) ;
        }
        
        //Caso: sea el último vuelo de varios vuelos
        if( vueloActual.destino.same( dest ) && solucion.size() > 0 ){
            Vuelo ultimoVuelo = solucion.get(solucion.size()-1); 
            horaInicioOrigen = ultimoVuelo.fechaLlegada;
            horaFinOrigen = vueloActual.fechaSalida;
            horaInicioDestino = vueloActual.fechaLlegada;
            horaFinDestino = new Fecha( vueloActual.fechaLlegada , Constantes.TOLERANCIA ) ;
        }
        
        //verificar que el almacen origen tenga disponibilidad hasta que salga el vuelo
        if( almacenDisponible(almacenOrigen, horaInicioOrigen, horaFinOrigen) ){
            disponibleOrigen = true;
        }
            
        //verificar que el almacen destino tenga disponibilidad hasta que recojan el paquete
        if( almacenDisponible( dest , horaInicioDestino, horaFinDestino) ){
            disponibleDestino = true;
        }
        
        return disponibleDestino && disponibleOrigen ;
    }    
    
    private Vuelo getLast(){
        return solucion.get( solucion.size() - 1 ) ;
    }
    
    private ArrayList<Vuelo> getCandidatos( Fecha fechaRegistro ){
        ArrayList<Vuelo> resp = new ArrayList<Vuelo>();
        Almacen origen = ( solucion.isEmpty() ? or : getLast().destino ) ;
        Fecha fechaBase ;
        int diasMax = ( continental == 1 ? 1 : 2 ) ;

        for( Vuelo v : LinKernighan.arVuelo ){
            fechaBase = ( solucion.isEmpty() ? fechaRegistro : getLast().fechaLlegada ) ;

            if( v.origen.same( origen ) )
                if( fechaBase.esMenorQue( v.fechaSalida ) )
                    if( v.fechaLlegada.esMenorQue( fechaRegistro.agregarDias( diasMax ) ) )
                        if( v.libre() )
                            if ( verificarDisponibilidadAlmacenes( v , fechaRegistro ))
                                    if( !usados.contains( v ) )
                                        resp.add( v ) ;
        }
        return resp;
    }

    private class CustomComparator implements Comparator<Vuelo>{
        @Override 
        public int compare(Vuelo o1, Vuelo o2) {
            int solucion=0;
            if (o1.costo < o2.costo){
                solucion = 1;
            }else if (o1.costo > o2.costo)
                solucion = -1;
            else if (o1.costo == o2.costo && o1.duracion < o2.duracion)
                solucion = 1;
            else if (o1.costo == o2.costo && o1.duracion > o2.duracion)
                solucion = -1;
            else if (o1.costo == o2.costo && o1.duracion == o2.duracion)
                solucion = 0;
            return solucion;
            //throw new UnsupportedOperationException("Not supported yet.");
        }
        
    }
    
    private ArrayList<Vuelo> ordenarCandidatos(ArrayList<Vuelo> arrV){
        Collections.sort( arrV , new CustomComparator() ) ;
        return arrV ;
    }
    
    private ArrayList<Vuelo> cortarCandidatos( ArrayList<Vuelo> arrV ){
        if ( arrV.size() > 2 ){
            int newSize = (int)( arrV.size() * alpha ) ;
            List<Vuelo> aux = null ;
            aux = arrV.subList( 0 , newSize ) ;
            ArrayList<Vuelo> rcl = new ArrayList<Vuelo>() ;
            rcl.addAll( aux ) ;
            return rcl ;
        }else{
            return arrV ;
        }
    }
    
    public void init( Almacen origen , Almacen destino ){
        solucion = new ArrayList<Vuelo>() ;
        solucionBest = new ArrayList<Vuelo>() ;
        usados = new ArrayList<Vuelo>() ;
        or = origen ;
        dest = destino ;
        continental = ( origen.distinctContinent( destino ) ? 1 : 0 ) ;
    }
    
    public void clear(){
        solucion.clear() ;
        usados.clear() ;
    }
    
    public int getRandom( int maximo ){
        Random r = new Random() ;
        return r.nextInt( maximo ) ;
    }
    
    private void removeLast(){
        solucion.remove( solucion.size() - 1 ) ;
    }
    
    private boolean mejora(){
        return ( funObj( solucion ) < funObj( solucionBest ) ) ;
    }
    
    public Ruta generarRutaGrasp(Almacen origen, Almacen destino, Fecha fechaCreacion){
        ArrayList<Vuelo> rcl;
        ArrayList<Vuelo> candidatos = new ArrayList<Vuelo>();
        
        Vuelo elegido;
        Vuelo vueloAnteriorSF;
        int noExisteRuta=0;
        
        int max_iteraciones = getMaxIteraciones() ;
        init( origen , destino ) ;
        
        for(int i = 0; i < max_iteraciones; i++){
            clear() ;
            
            while(solucion.isEmpty() || getLast().destino.diff( destino ) ){
                candidatos = getCandidatos( fechaCreacion ) ;
                
                if( candidatos.isEmpty() ){
                    if( solucion.size() > 0 ){
                        removeLast() ;
                        continue;
                    }else if( solucion.isEmpty() ){
                        noExisteRuta = 1 ;
                        break;
                    }
                }

                ordenarCandidatos( candidatos ) ;
                rcl = cortarCandidatos( candidatos ) ;
                elegido = rcl.get( getRandom( rcl.size() ) ) ;
                solucion.add( elegido ) ;
                usados.add( elegido ) ;
            }

            //Busca salir del bucle de iteraciones, ya que el origen no encuentra ruta posible
            if( noExisteRuta == 1 ) break;

            if( solucionBest.isEmpty() || mejora() ){
                solucionBest = solucion;
            }
        }
        
        Ruta rutaG=null;
        if (!solucionBest.isEmpty()){
            
            System.out.println("*******************************Se encontró ruta!");
            rutaG = new Ruta( origen , destino ) ;
            
            rutaG.fechaSalida = (Fecha)solucionBest.get(0).fechaSalida.clone() ;
            rutaG.fechaLlegada = (Fecha)solucionBest.get(solucionBest.size()-1).fechaLlegada.clone() ;

            int i = 0 ;
            for( Vuelo v : solucionBest ){
//            for(int i = 0; i < solucionBest.size(); i++){
                LinKernighan.arVueloXRuta.add( new VueloXRuta( rutaG, v ) );

                //Si es el primer vuelo
                if(i == 0){
                    LinKernighan.arReserva.add(new ReservaAlmacen(origen, null, fechaCreacion, v.fechaSalida, null, null, 0));
                }
                //Si es el último vuelo
                else if( i == solucionBest.size() - 1){
                    Fecha fechaMaxRecojo = new Fecha( v.fechaLlegada , Constantes.TOLERANCIA ) ;
                    LinKernighan.arReserva.add(new ReservaAlmacen( v.destino, null, v.fechaLlegada, fechaMaxRecojo,null,null,0));

                    /*else if(continental == 1)
                        arReserva.add(new ReservaAlmacen(solucionBest.get(solucionBest.size() - 1).destino, null, solucionBest.get(solucionBest.size() - 1).fechaSalida, fechaCreacion.mas1o2Dias(2), null, null, 0));
                        * */
                }
                //Si es cualquier otro vuelo
                else{
                    //El almacem será el almacen destino del vuelo anterior
                    vueloAnteriorSF = solucionBest.get(i-1);
                    LinKernighan.arReserva.add(new ReservaAlmacen(vueloAnteriorSF.destino, null, vueloAnteriorSF.fechaLlegada, v.fechaSalida, null, null, 0));
                }
                i++ ;
            }
            
            //Ahora lleno los vuelos de la ruta
            for( Vuelo v : solucionBest ){
                rutaG.vuelos.add( v ) ;
            }
        }

        return rutaG;
    }

}
